package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * todo
 *
 * @author wanwei
 * @since 2022-03-12 11:17
 */
public class AN62不同路径 {
    public static void main(String[] args) {

//        List<String> total = new ArrayList<>();
//        uniquePaths(5, 4, 1, 1, total);
//        System.out.println(total.size());
//        total = new ArrayList<>();
//        uniquePaths(4, 4, 1, 1, total);
//        System.out.println(total.size());
//        total = new ArrayList<>();
//        uniquePaths(3, 5, 1, 1, total);
//        System.out.println(total.size());


        //System.out.println(uniquePaths2(51, 9));
        int m = 51, n = 9;
        if(m>n){
            int t = n;
            n = m;
            m = t;
        }

        Map<String, Integer> map = new HashMap<>();
        for (int i = 2; i < m; i++) {
            for (int j = i; j < n; j++) {
                int total = uniquePaths2(i, j, map);
                map.put(i + "," + j, total);
                map.put(j + "," + i, total);
            }
        }
        System.out.println(uniquePaths2(m, n, map));
    }


    /**
     * 1.使用回溯  如果MN过大 回溯深度太深 内存过大
     *
     * @param m
     * @param n
     * @return
     */
    public static void uniquePaths(int m, int n, int x, int y, List<String> total) {
        if (x == m && y == n) {
            total.add("1");
            return;
        }
        if (x < m && y < n) {
            uniquePaths(m, n, x + 1, y, total);
            uniquePaths(m, n, x, y + 1, total);
        } else if (x == m) {
            uniquePaths(m, n, x, y + 1, total);
        } else if (y == n) {
            uniquePaths(m, n, x + 1, y, total);
        }
    }

    /**
     * 2.找到规律  (m,n) = (m-1,n) + (m,n-1) 如果使用递归 层次依旧可能很深
     * 使用递推 并添加缓存
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePaths2(int m, int n, Map<String, Integer> map) {
        if (m == 1 || n == 1) {
            return 1;
        }
        Integer total = map.get(m + "," + n);
        if (total != null) {
            return total;
        }
        return uniquePaths2(m - 1, n, map) + uniquePaths2(m, n - 1, map);
    }
}
